#有N种物品和一个容量为C的背包，每种物品[数量有限]
#第i件物品的体积是v[i]，价值是w[i]，数量是s[i]
#问选择哪些物品，每件物品选择多少件，可使得总价值最大
#其实就是在0-1背包问题的基础上，增加了每件物品可以选择的[有限次数](在容量允许的前提下)
N=2
C=5
v=[1,2]
w=[1,2]
s=[2,1]
#输出:4
def muti_dimension_Knapsack(N,C,v,w,s):
    #dp
    dp=[[0 for _ in range(C+1)] for _ in range(N)]
    #先考虑第一行
    for i in range(C+1):
        if int(i)%int(v[0])==0:
            #可以除尽
            number=int(i/v[0])
            if number<=s[0]:
                dp[0][i]=number*w[0]
            else:
                dp[0][i]=s[0]*w[0]
    for i in range(1,N):
        for j in range(C+1):
            maxValue = dp[i - 1][j]
            k = 1
            while k * v[i] >= 0 and k * v[i] <= j and k<=s[i]:
                if dp[i - 1][j - k * v[i]] + w[i] * k > maxValue:
                    maxValue = dp[i - 1][j - k * v[i]] + w[i] * k
                k += 1
            dp[i][j] = maxValue
    print(dp)
#二维背包
def muti_dimension_Knapsack1(N,C,v,w,s):
    #dp
    dp=[[0 for _ in range(C+1)] for _ in range(2)]
    #先考虑第一行
    for i in range(C+1):
        if int(i)%int(v[0])==0:
            #可以除尽
            number=int(i/v[0])
            if number<=s[0]:
                dp[0][i]=number*w[0]
            else:
                dp[0][i]=s[0]*w[0]
    for i in range(1,N):
        for j in range(C+1):
            maxValue = dp[(i - 1)&1][j]
            k = 1
            while k * v[i] >= 0 and k * v[i] <= j and k<=s[i]:
                if dp[(i - 1)&1][j - k * v[i]] + w[i] * k > maxValue:
                    maxValue = dp[(i - 1)&1][j - k * v[i]] + w[i] * k
                k += 1
            dp[i&1][j] = maxValue
    print(dp)
muti_dimension_Knapsack(N,C,v,w,s)